⟸ pàgina anterior ⟸

Exercici 2 (Tasca 4).

(ambiguity, context-free languages)

Gramàtiques incontextuals ambigües

Demostreu que les gramàtiques següents són ambigües.

1. \left\{\begin{array}{ccl} S &\to& aSb \mid B \\ B &\to& bAa \mid bCb \mid \lambda \\ A &\to& aAbA \mid bAaA \mid \lambda \\ C &\to& Aaa \mid aAa \mid aaA \end{array}\right.
2. \left\{\begin{array}{ccl} S &\to& aU_1 \mid aS \mid bZ_1 \mid bS \\ Z_1 &\to& aU_2 \mid bF \\ U_1 &\to& bU_2 \\ U_2 &\to& bF\mid b \\ F &\to& aF \mid bF \mid a \mid b \end{array}\right.
3. \left\{\begin{array}{ccl} S &\to& AaBA \mid ABaA \mid ACA \mid AbabA \\ B &\to& bb \\ C &\to& bB \\ A &\to& aA \mid bA \mid \lambda \end{array}\right.
4. \left\{\begin{array}{ccl} S &\to& aU_1 \mid aS \mid bZ_1 \mid bS \\ Z_1 &\to& aU_2 \mid bZ_2 \\ U_1 &\to& bU_2 \\ U_2 &\to& bF \\ Z_2 &\to& aF \mid bF \\ F &\to& aF \mid bF \mid \lambda \end{array}\right.